package SortAlgorithm;

/**
 * @author gao
 * @date 2025/11/7 10:09
 */

public class QuickSort implements Sort {

    @Override
    public void sort(int[] nums) {
        quick(nums, 0, nums.length - 1);
    }

    /**
     * 快速排序的递归实现方法
     * @param nums 待排序的数组
     * @param start 排序的起始位置
     * @param end 排序的结束位置
     */
    public void quick(int[] nums, int start, int end) {
        // 如果起始位置大于或等于结束位置，说明已经排序完成，直接返回
        if (start >= end) {
            return;
        }

        // 获取分区点，将数组分为两部分
        int par = partition(nums, start, end);
        // 对分区点左边的子数组进行递归排序
        quick(nums, start, par - 1);
        // 对分区点右边的子数组进行递归排序
        quick(nums, par + 1, end);
    }

    /**
     * 快速排序中的分区函数，用于确定基准元素的位置并分区数组
     * @param nums 待排序的数组
     * @param left 分区的左边界索引
     * @param right 分区的右边界索引
     * @return 基准元素最终所在的索引位置
     */
    private int partition(int[] nums, int left, int right) {
        // 初始化左指针i，并保存基准元素的值
        int i = left;
        int tmp = nums[left];

        // 当左右指针未相遇时，继续分区操作
        while (left < right) {
            // 从右向左寻找第一个小于基准元素的元素
            while (left < right && nums[right] >= tmp) {
                right--;
            }
            // 从左向右寻找第一个大于基准元素的元素
            while (left < right && nums[left] <= tmp) {
                left++;
            }
            // 交换找到的两个元素
            swap(nums, left, right);
        }
        // 将基准元素放到正确的位置（左右指针相遇处）
        swap(nums, left, i);
        // 返回基准元素的最终位置
        return left;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}